#include <bits/stdc++.h>

using namespace std;

int main()
{

    vector<int> v = {99, 8, 3, 1, 4, 2, 0};

    // sort: 不稳定的排序
    // size < 16 插入排序
    // size > 16 递归深度为0 ,堆排序
    // size > 16 递归深度不为0,快速排序
    // sort(v.begin(),v.end());
    // for_each(v.begin(), v.end(), [](int &a)
    //          { cout << a << " "; });
    // cout<<endl;

    // stable_sort: 稳定的排序算法
    //  size < 15 插入排序
    //  size > 15 分组 插入 归并
    //  stable_sort(v.begin(), v.end());
    //  for_each(v.begin(), v.end(), [](int &a)
    //           { cout << a << " "; });
    //  cout << endl;

    // partial_sort: 排序，直到前n个元素就位
    // partial_sort(v.begin(), v.begin() + 2, v.end());
    // for_each(v.begin(), v.end(), [](int &a)
    //          { cout << a << " "; });
    // cout << endl;

    // nth_element:只排第n个元素
    // nth_element(v.begin(), v.begin() + 1, v.end());
    // for_each(v.begin(), v.end(), [](int &a)
    //          { cout << a << " "; });
    // cout << endl;

    // make_heap:构建堆
    make_heap(v.begin(), v.end(), std::greater<int>());
    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;

    // push_heap：往堆里面塞元素 ： 在此之前需要push_back 塞入一个元素再构建堆
    // make_heap(v.begin(), v.end());
    // v.push_back(12);
    // push_heap(v.begin(), v.end()); // 塞入一个新元素以后，再构建堆
    // for_each(v.begin(), v.end(), [](int &a)
    //          { cout << a << " "; });
    // cout << endl;

    // pop_heap:从heap移除一个元素
    // make_heap(v.begin(), v.end());
    // v.push_back(12);
    // push_heap(v.begin(), v.end()); // 塞入一个新元素以后，再构建堆
    // pop_heap(v.begin(), v.end());
    // for_each(v.begin(), v.end(), [](int &a)
    //          { cout << a << " "; });
    // cout << endl;

    // sort_heap:对heap进行排序，排序后不再是堆
    make_heap(v.begin(), v.end());
    v.push_back(12);
    push_heap(v.begin(), v.end()); // 塞入一个新元素以后，再构建堆
    sort_heap(v.begin(), v.end());
    for_each(v.begin(), v.end(), [](int &a)
             { cout << a << " "; });
    cout << endl;
    return 0;
}